Reconfigurable hardware is used in adaptive computing and other applications to implement logic circuit functions. A given set of reconfigurable hardware, which may be based on field programmable gate arrays (FPGAs) or other similar devices, can be reconfigured so as to provide different logic functions at different times, thereby in effect providing the functionality of a complex circuit which would otherwise require substantially more hardware. Reconfigurable hardware based on FPGAs is described in, for example, J. H. Mayer, "Reconfigurable computing redefines design flexibility," Computer Design, pp. 49-52, February 1997; J. Rosenberg, "Implementing Cache Logic.TM. with FPGAs," Atmel Application Note 0461A, pp. 7-11 to 7-14; and B. K. Fawcett, "Applications of Reconfigurable Logic," in "More FPGAs," W. R. Moore and W. Luk, eds., Abingdon EE & CS Books, Oxford, England, pp. 57-69, 1994; all of which are incorporated by reference herein.
In a typical adaptive computing application, a preprocessing phase is used to produce a circuit model, referred to as a netlist, which is loaded into the reconfigurable hardware such that the hardware provides the functionality of a particular circuit. Unfortunately, conventional reconfigurable hardware platforms often have insufficient capacity to handle the entire netlist for a circuit of even moderate complexity. Although a type of reconfigurable hardware known as an emulator can provide a very large capacity, up to about six million gates, emulators are also very expensive, typically costing on the order of $0.75 per gate, and are therefore impractical for many important applications.
In order to avoid the need for a costly emulator, some applications partition a given circuit into stages, such that a less costly reconfigurable hardware platform may be used to implement each of the stages. FIG. 1 shows an example of such an application. A logic circuit 10 includes three distinct stages 12-1, 12-2 and 12-3 as shown. Each of the stages 12-1, 12-2 and 12-3 of the logic circuit 10 are implemented in turn using the same reconfigurable hardware 14. A partial netlist including information characterizing a given one of the stages is loaded into the reconfigurable hardware 14 in order to permit the hardware to perform processing operations for that stage. In this manner, the reconfigurable hardware 14 is shared by the stages 12-1, 12-2 and 12-3, and periodically reconfigured to provide the particular processing operations required in each of the stages. The technique illustrated in FIG. 1 is suitable for use in applications which can be naturally partitioned into stages, where each stage works with the data prepared by the previous stage, in a manner similar to the stages of a pipeline. See, for example, H. Schmit, "Incremental Reconfiguration for Pipelined Applications," IEEE Symposium on FPGAs for Custom Computing Machines, pp. 47-55, 1996.
Assuming that the logic functions used in each of the stages of a pipelined circuit structure such as that shown in FIG. 1 can be implemented in the available hardware, such an application can reuse the hardware by reconfiguring it for each stage. However, there are a number of problems with this type of approach. For example, partitioning a logic circuit into stages often requires a substantial amount of expensive manual design effort. Moreover, many important applications do not exhibit a pipelined structure which can be partitioned into identifiable stages. Even if a circuit does exhibit a pipelined structure, this structure may not be easy to recognize from a large netlist, or the size of the circuit may be such that no single stage can be accommodated by the available hardware. Current reconfigurable hardware techniques are thus not capable of processing large circuit netlists in an economical manner, and are therefore not readily utilizable in to many important applications.